package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_40_组合总和II {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_40_组合总和II().combinationSum2(new int[]{10,1,2,7,6,1,5},8));
        System.out.println(new 力扣_40_组合总和II().combinationSum2(new int[]{2,5,2,1,2},5));
        System.out.println(new 力扣_40_组合总和II().combinationSum2(new int[]{10,1,2,7,6,1,5},10));
        System.out.println(new 力扣_40_组合总和II().combinationSum2(new int[]{10,1,2,7,6,1,5},1));


        System.out.println(new 力扣_40_组合总和II().combinationSum2(new int[]{2,5,2,1,2},5));
    }

    /**
    题目：给定一个候选人编号的集合 candidates 和一个目标数 target ，
     找出 candidates 中所有可以使数字和为 target 的组合。
     candidates 中的每个数字在每个组合中只能使用 一次 。
     注意：解集不能包含重复的组合。 

     示例 1:
     输入: candidates = [10,1,2,7,6,1,5], target = 8,
     输出:  [ [1,1,6], [1,2,5], [1,7],  [2,6]  ]

     示例 2:
     输入: candidates = [2,5,2,1,2], target = 5,
     输出:  [ [1,2,2], [5]  ]

    分析：【P 💜💜💜💜】
       1.回溯法3步曲：
             1.一条路走到黑
             2.回退一步
             3.另寻他路
            难点：跳过重复值：i>index 非常之精辟：当这里是开始  ，且连续相同元素时，start开始已经将后续相同元素的情况遍历完了，则没必要进入递归，
            --执行用时：0 ms, 在所有 Java 提交中击败了100%的用户

    边界值 & 注意点：
        1.都是正数
             1 <= candidates.length <= 100
             1 <= candidates[i] <= 50
             1 <= target <= 30
        2.出错： candidates = [1,2,2,2,2,5], target = 4,   //这里相同值，应不应该跳过，成为了难题   解：i>index && candidates[i] == candidates[i-1]跳过
     **/
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res =new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();
        dfs(candidates,res,deque,0,target);
        return res;
    }

    private void dfs(int[] candidates, List<List<Integer>> res, Deque<Integer> deque, int start, int target) {
        if(target>0){
            for (int j = start; j < candidates.length; j++) {//不能向后看
                if(target<candidates[j] ) return; //位图保证不重复
                if(start<j && candidates[j]==candidates[j-1] )  // i>index 非常之精辟：这里是开始两个值相同，相同元素时，
                    // start开始已经将后续相同元素的情况遍历完了，则没必要进入递归，
                    continue;
                deque.add(candidates[j]);
                dfs(candidates,res,deque, j+1,target-candidates[j]);
                deque.pollLast();
            }
        }else if(target==0){
            res.add(new ArrayList<>(deque));
        }
    }
}
